//给你一个 m x n 的二进制矩阵 grid 。 
//
// 如果矩阵中一行或者一列从前往后与从后往前读是一样的，那么我们称这一行或者这一列是 回文 的。 
//
// 你可以将 grid 中任意格子的值 翻转 ，也就是将格子里的值从 0 变成 1 ，或者从 1 变成 0 。 
//
// 请你返回 最少 翻转次数，使得矩阵 要么 所有行是 回文的 ，要么所有列是 回文的 。 
//
// 
//
// 示例 1： 
//
// 
// 输入：grid = [[1,0,0],[0,0,0],[0,0,1]] 
// 
//
// 输出：2 
//
// 解释： 
//
// 
//
// 将高亮的格子翻转，得到所有行都是回文的。 
//
// 示例 2： 
//
// 
// 输入：grid = [[0,1],[0,1],[0,0]] 
// 
//
// 输出：1 
//
// 解释： 
//
// 
//
// 将高亮的格子翻转，得到所有列都是回文的。 
//
// 示例 3： 
//
// 
// 输入：grid = [[1],[0]] 
// 
//
// 输出：0 
//
// 解释： 
//
// 所有行已经是回文的。 
//
// 
//
// 提示： 
//
// 
// m == grid.length 
// n == grid[i].length 
// 1 <= m * n <= 2 * 10⁵ 
// 0 <= grid[i][j] <= 1 
// 
//
// Related Topics 数组 双指针 矩阵 👍 29 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2024-11-15 19:43:17
 * @description 3239.最少翻转次数使二进制矩阵回文 I
 
 */
 
public class MinimumNumberOfFlipsToMakeBinaryGridPalindromicI {
    public static void main(String[] args) {
    //测试代码
    MinimumNumberOfFlipsToMakeBinaryGridPalindromicI fun = new MinimumNumberOfFlipsToMakeBinaryGridPalindromicI();
    Solution solution= fun.new Solution();
    solution.minFlips(new int[][]{{0,1},{0,1},{0,0}});
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        /*
        * 其实每个位置的0，1，只影响和他对称的位置，贪心每个位置最小
        * 相当于每次更新四个位置，最理想的情况正好每次都分割成4个
        * 不理想的情况是，每次更新2个或者1个
        * 如果只有一个，或者都相等就不需要改，计算这几个数中出现次数最少的那个数
        * */
    //这个计算的是整体，不合题意
    public int minFlips1(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int res=0;
        for (int i = 0; i < m / 2; i++) {
            for (int j = 0; j < n / 2; j++) {
                int count=0;
                int t1=0;
                int t0=0;
                t1+=grid[i][j];
                t0+=grid[j][j];
                if(m-i-1!=i){
                    t1+=grid[m-i-1][j];
                    t0+=grid[m-i-1][j];
                    count++;
                }
                if(n-j-1!=j){
                    t1+=grid[i][n-j-1];
                    t0+=grid[i][n-j-1];
                    count++;
                }
                if(m-i-1!=i&&n-j-1!=j){
                    t1+=grid[m-i-1][n-j-1];
                    t0+=grid[m-i-1][n-j-1];
                    count++;
                }
                if(count==1) {
                    res += (t1 != t0 ? 1 : 0);
                }
                if(count==3){
                    res+=(t1!=t0?Math.min(t1,t0):2);
                }
            }
        }
        return res;
    }


    public int minFlips(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int r=0,c=0;
        for (int i = 0; i < m ; i++) {
            for (int j = 0; j < n; j++) {
                if((grid[i][j]^grid[i][n-j-1])!=0) c++;
                if((grid[i][j]^grid[m-i-1][j])!=0) r++;

            }
        }
        return Math.min(r,c)/2;
    }

    public int minFlips2(int[][] grid) {
        int rowCnt = 0, colCnt = 0;
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j1 = 0, j2 = n - 1; j1 < j2; j1++, j2--) {
                if ((grid[i][j1] ^ grid[i][j2]) != 0) {
                    rowCnt++;
                }
            }
        }
        for (int j = 0; j < n; j++) {
            for (int i1 = 0, i2 = m - 1; i1 < i2; i1++, i2--) {
                if ((grid[i1][j] ^ grid[i2][j]) != 0) {
                    colCnt++;
                }
            }
        }
        return Math.min(colCnt, rowCnt);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
